package 算法.leetcode.labuladong.数组和链表;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lchenglong
 * @date 2022/6/16
 */
public class 找到字符串中所有字母异位词 {
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            Map<Character,Integer> need = new HashMap<>(26);
            Map<Character,Integer> window = new HashMap<>(26);
            for (Character c: p.toCharArray()){
                need.put(c,need.get(c)==null?1:need.get(c)+1);
            }
            int left=0,right=0,valid=0;
            List<Integer> ans = new ArrayList<>();
            while (right<s.length()){
                //移入一个字符串,扩大窗口
                char c = s.charAt(right);
                right++;
                // 窗口内的一系列更新
                if (need.containsKey(c)){
                    window.put(c,window.get(c)==null?1:window.get(c)+1);
                    // 字符数符合条件
                    if (window.get(c).equals(need.get(c)))valid++;
                }
                // 是否满足窗口收缩
                while (right-left>=p.length()){
                    if (valid == need.size())
                        ans.add(left);
                    // 窗口收缩
                    char d = s.charAt(left);
                    left++;
                    // 窗口内的数据进行更新
                    if (need.containsKey(d)){
                        if (need.get(d).equals(window.get(d)))valid--;
                        window.put(d,window.get(d)-1);
                    }
                }
            }
            return ans;
        }
    }
}
